package RSA;

import java.math.BigInteger;
import java.util.Random;

public class MillerRabinPrime {
    private static final int CERTAINTY = 20; // 循环次数，提高判断素数的准确性

    public static void main(String[] args) {
        int bitLength = 128; // 指定生成的大素数的位数
        BigInteger prime = generatePrime(bitLength);
        System.out.println("生成的大素数为: " + prime);
    }


    public static BigInteger generatePrime(int bitLength) {
        Random random = new Random();
        BigInteger prime;

        do {
            prime = new BigInteger(bitLength, random);
            prime = prime.setBit(0); // 设置最低位为1，确保生成的数为奇数
        } while (!isPrime(prime));
        return prime;
    }

    public static boolean isPrime(BigInteger n) {
        if (n.equals(BigInteger.valueOf(2))) {
            return true;
        }

        if (n.compareTo(BigInteger.ONE) <= 0 || n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            return false;
        }

        BigInteger d = n.subtract(BigInteger.ONE);
        int r = 0;
        while (d.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.valueOf(2));
            r++;
        }

        for (int i = 0; i < CERTAINTY; i++) {
            BigInteger a = getRandomBase(n);
            BigInteger x = a.modPow(d, n);

            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }

            boolean isComposite = true;
            for (int j = 0; j < r - 1; j++) {
                x = x.modPow(BigInteger.valueOf(2), n);
                if (x.equals(BigInteger.ONE)) {
                    return false;
                }
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    isComposite = false;
                    break;
                }
            }

            if (isComposite) {
                return false;
            }
        }

        return true;
    }

    private static BigInteger getRandomBase(BigInteger n) {
        Random random = new Random();
        BigInteger a;
        do {
            a = new BigInteger(n.bitLength(), random);
        } while (a.compareTo(BigInteger.ONE) <= 0 || a.compareTo(n) >= 0);
        return a;
    }
}
